package Other.DP;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author:gao
 * @date:2020/7/10
 * @time:19:01
 * @version:0.0.1
 * @description:none
 */


//300. 最长上升子序列
public class LengthOfLIS {

}

//未优化的
class Solution2222 {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int ans =-1;
        int[] dp = new int[len];
        //应该熟悉这种，在大循环内套小循环的dp
        //大循环控制总体，小循环找dp[i]和前面的关系
        for (int i = 0; i <len ; i++) {
            int max = -1;
            for(int j =0;j<i;j++){
                if(nums[i]>nums[j]) max = Math.max(max,dp[j]);
            }
            dp[i]=max+1;
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
}

//方法2没看
